package 栈;

import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/basic-calculator/comments/
 *
 * 实现一个基本的计算器来计算一个简单的字符串表达式的值。
 * 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格.
 * 示例 1:
 * 输入: "1 + 1"
 * 输出: 2
 *
 * 示例 2:
 * 输入: " 2-1+2 "
 * 输出: 3
 *
 * 示例 3:
 * 输入: "(1+(4+5+2)-3)+(6+8)"
 * 输出: 23
 *
 * 解题思路:
 * 1. 遍历字符串，如果是数字入栈
 *
 */
public class _224_基本计算器 {

    public static void main(String[] args) {
        calculate("100+(4+5+2)-3+(6+8)");
    }

    public static int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int length = s.length();
        int operand = 0;
        int result = 0;
        int sign = 1;
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                // 123 >> 120 + 3 >> 100 + 20 + 3
                // 1+0 ==> 10+2 ==> 120+3
                operand = 10 * operand + (int) (ch - '0');
            } else if (ch == '+') {
                result += sign * operand;
                sign = 1;
                operand = 0;
            } else if (ch == '-') {
                result += sign * operand;
                sign = -1;
                operand = 0;
            } else if (ch == '(') {
                stack.push(result);
                stack.push(sign);
                sign = 1;
                result = 0;
            } else if (ch == ')') {
                result += sign * operand;
                result *= stack.pop();
                result += stack.pop();
                operand = 0;
            }
        }
        return result + (sign * operand);
    }
}
